#include <ctime>
#include <iostream>
#include <list>
#include <map>
using namespace std;

class LRUCache{
public:
    LRUCache(int capacity)
    :_capacity(capacity)
    {
    }
    list<int>::iterator find_key(int key){
        auto it = list_keys.begin();
        for(;it != list_keys.end(); ++it){
            if(*it == key){
                break;
            }
        }
        return it;
        
    }

    void put(int key,int val){
        auto it = find_key(key);
        if(it != list_keys.end()){
            //找到了
            list_keys.splice(list_keys.begin(),list_keys,it);//将值放到链表头部
            _key_v[key] = val;            
        }else{
            //没找到
            list_keys.push_front(key); //插入链表头部
            _key_v[key] = val;
            if(list_keys.size() > _capacity){
                int last_key = list_keys.back();
                list_keys.pop_back(); //超出容量上限，将表尾的删除
            }
        }
    }
    void display(){
        for(auto &i : list_keys){
            cout <<'[' <<i <<','<<_key_v[i]<<"] ";
        }
        cout<<endl;
    }

    int get(int key){
        auto it = find_key(key);
        if(it != list_keys.end()){
            list_keys.splice(list_keys.begin(),list_keys,it);//将值放到链表头部
            return _key_v[*it];
        }else{
            //不在缓冲区：
            int val=_key_v[key];
            list_keys.push_front(key);
            if(list_keys.size() > _capacity){
                int last_key = list_keys.back();
                list_keys.pop_back(); //超出容量上限，将表尾的删除
            }
            return val;
        }
    }
private:
    int _capacity;
    map<int,int> _key_v;
    list<int> list_keys;
};
void test(){
    LRUCache lru(3);
    lru.put(1,2);
    lru.put(2,3);
    lru.put(3,4);
    lru.put(4,5);
    lru.display();
    lru.get(3);
    lru.get(1);
    lru.display();
}

int main()
{
    

    test ();
    return 0;
}

